/**
 * @author ChaP
 * @date 2019/06/09
 * @describe:
 */
package CodingTest.AC20190609;

import java.util.Arrays;

/**
 * leetcode - 475
 * 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

 现在，给出位于一条水平线上的房屋和供暖器的位置，找到可以覆盖所有房屋的最小加热半径。

 所以，你的输入将会是房屋和供暖器的位置。你将输出供暖器的最小加热半径。

 说明:

 给出的房屋和供暖器的数目是非负数且不会超过 25000。
 给出的房屋和供暖器的位置均是非负数且不会超过10^9。
 只要房屋位于供暖器的半径内(包括在边缘上)，它就可以得到供暖。
 所有供暖器都遵循你的半径标准，加热的半径也一样。
 示例 1:

 输入: [1,2,3],[2]
 输出: 1
 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
 示例 2:

 输入: [1,2,3,4],[1,4]
 输出: 1
 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/heaters
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class findRadius {
    //双指针法
    public int findRadius(int[] houses,int[] heaters) {
        if(heaters.length == 0) return 0;
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int holen = houses.length;
        int helen = heaters.length;
        int result = 0;
        if(houses[0]>=heaters[helen-1]){
            return houses[holen-1] - heaters[helen-1];
        }
        if(heaters[0]>=houses[holen-1]){
            return heaters[0]-houses[0];
        }
        int i = 0,j =0;
        while(i<holen &&j<helen){
            //找到>=houses[i]的第一个数
            while(j<helen && heaters[j]< houses[i]){
                j++;
            }
            if(j == helen) break;
            int min = j-1>=0 ? Math.min(houses[i]-heaters[j-1],heaters[j]-houses[i]):(heaters[j]-houses[i]);
            result = Math.max(result,min);
            i++;
        }
        if(i<holen){
            result = Math.max(result,houses[holen-1]-heaters[helen-1]);
        }
        return result;
    }
}
